import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/26 16:23
 * @description 差分数组
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] segments = {{4,16,12},{9,10,15},{18,19,13},{3,13,20},{12,16,3},{2,10,10},{3,11,4},{13,16,6}};
        solution.splitPainting(segments);
    }
    public List<List<Long>> splitPainting(int[][] segments) {
        // 差分数组右端点值
        int max = 0;
        // 需要分割的点，TreeSet即可排序端点，又可弹出左端点
        TreeSet<Integer> set = new TreeSet<>();
        for (int[] segment: segments) {
            if (segment[1] > max) {
                max = segment[1];
            }
            set.add(segment[0]);
            set.add(segment[1]);
        }
        // 差分数组，从这里开始直接用long，不然可能数据溢出
        long[] diff = new long[max + 1];
        for(int[] segment: segments) {
            diff[segment[0]] += segment[2];
            diff[segment[1]] -= segment[2];
        }
        long[] preSum = new long[max + 1];
        for(int i = 1; i <= max; i++) {
            preSum[i] = preSum[i-1] + diff[i];
        }
        List<List<Long>> ans = new ArrayList<>();
        while (set.size() > 1) {
            // 左边界获取并删除，右边界获取不删除
            int l = set.pollFirst(), r = set.first();
            // 区间[l, r)颜色为0，剔除
            if (preSum[l] == 0) {
                continue;
            }
            ans.add(Arrays.asList((long)l, (long)r, preSum[l]));
        }
        return ans;
    }
}
